#include <stdlib.h>

#define TRUE 1
#define FALSE 0

struct linkList
{
    /* data */
    // 头结点的val存储链表长度
    int val;
    struct linkList *next;
};

// 包含头节点
void InitList(struct linkList *head)
{
    head->val = 0;
    head->next = NULL;
}

// 判断链表是否为空
int ListEmpty(struct linkList *head)
{
    return head->next == NULL ? TRUE : FALSE;
}

// 清空链表
void ClearList(struct linkList *head)
{
    struct linkList *temp = head->next;
    while (temp != NULL)
    {
        struct linkList *node = temp;
        temp = temp->next;
        free(node);
    }
}

// 获取指定索引位置的元素,下标从1开始
int GetElem(struct linkList list, int addr, int *val)
{
    if (list.val < addr || addr < 1)
    {
        return FALSE;
    }

    for (int i = 0; i < addr; i++)
    {
        list = *(list.next);
    }
    *val = list.val;
    return TRUE;
}

// 判断链表中是否存在特定值
int LocateElem(struct linkList *head, int val)
{
    struct linkList *node = head->next;
    while (node != NULL)
    {
        if (node->val == val)
        {
            return TRUE;
        }
    }
    return FALSE;
}

// 插入元素到指定索引位置，链表的索引下标从1开始
int InsertList(struct linkList *head, int index, int val)
{
    if (head->val + 1 < index)
        return FALSE;
    struct linkList *node = head;
    for (int i = 0; i < index - 1; i++)
    {
        node = node->next;
    }
    struct linkList *temp = (struct linkList *)malloc(sizeof(struct linkList));
    temp->val = val;
    temp->next = node->next;
    node->next = temp;
    head->val++;
    return TRUE;
}

// 将数组元素重构成链表
struct linkList *CreateLinkList(int *list, int len)
{
    struct linkList *head = (struct linkList *)malloc(sizeof(struct linkList));
    struct linkList *node = head;
    InitList(head);
    for (int i = 0; i < len; i++)
    {
        InsertList(node,i+1,list[i]);
    }
    return head;
}

// 遍历链表
void PrintLinkList(struct linkList head)
{
    struct linkList *node = head.next;
    while(node != NULL)
    {    
        printf("%d ",node->val);
        node = node->next;    
    }
}

// 返回链表长度
int ListLength(struct linkList head)
{
    return head.val;
}

// 求最大值
int MaxList(struct linkList head)
{
    if(head.val == 0)
        return 0;
    
    struct linkList *node = head.next;
    int max = node->val;
    while (node != NULL)
    {
        /* code */
        if(node->val > max)
            max = node->val;
        node = node->next;
    }
    return max;
}

// 两个顺序表的归并算法,递增的情况
struct linkList* Merge(struct linkList *L1, struct linkList *L2)
{
    struct linkList *L3 = (struct linkList *)malloc(sizeof(struct linkList));
    InitList(L3);
    // 从除头节点以外的第一个结点开始
    struct linkList *node1 = L1->next;
    struct linkList *node2 = L2->next;
    struct linkList *node3 = L3;

    // 归并排序算法
    while(node1 != NULL || node2 != NULL)
    {
        int temp = 0;
        if(node1!=NULL && node1->val < node2->val)
        {
            temp = node1->val;
            node1 = node1->next;
        }
        else
        {
            temp = node2->val;
            node2 = node2->next;
        } 
        struct linkList *new_node = (struct linkList *)malloc(sizeof(struct linkList));
        new_node->val = temp;
        new_node->next = NULL;
        node3->next = new_node;
        node3 = node3->next;
        // L3的链表长度增加
        L3->val ++;
    }
    return L3;
}

